home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / gnustuff / tos / progut~1 / gperf.zoo / src / key-list.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1991-09-25  |  39.2 KB  |  1,153 lines
  1. /* Routines for building, ordering, and printing the keyword list.
  2.    Copyright (C) 1989 Free Software Foundation, Inc.
  3.    written by Douglas C. Schmidt (schmidt@ics.uci.edu)
  4.  
  5. This file is part of GNU GPERF.
  6.  
  7. GNU GPERF is free software; you can redistribute it and/or modify
  8. it under the terms of the GNU General Public License as published by
  9. the Free Software Foundation; either version 1, or (at your option)
  10. any later version.
  11.  
  12. GNU GPERF is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. GNU General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with GNU GPERF; see the file COPYING.  If not, write to
  19. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20.  
  21. #include <stdio.h>
  22. #include <builtin.h>
  23. #include <assert.h>
  24. #ifdef sparc
  25. #include <alloca.h>
  26. #endif
  27. #include "options.h"
  28. #include "read-line.h"
  29. #include "hash-table.h"
  30. #include "key-list.h"
  31. #include "trace.h"
  32.  
  33. /* Efficiently returns the least power of two greater than or equal to X! */
  34. #define POW(X) ((!X)?1:(X-=1,X|=X>>1,X|=X>>2,X|=X>>4,X|=X>>8,X|=X>>16,(++X)))
  35.  
  36. /* How wide the printed field width must be to contain the maximum hash value. */
  37. static int field_width = 0;
  38.  
  39. /* Destructor dumps diagnostics during debugging. */
  40.  
  41. Key_List::~Key_List (void) 
  42. { 
  43.   T (Trace t ("Key_List::~Key_List");)
  44.   if (option[DEBUG])
  45.     {
  46.       fprintf (stderr, "\nDumping key list information:\ntotal non-static linked keywords = %d"
  47.                "\ntotal keywords = %d\ntotal duplicates = %d\nmaximum key length = %d\n",
  48.                list_len, total_keys, total_duplicates, max_key_len);
  49.       dump ();
  50.       report_error ("End dumping list.\n\n");
  51.     }
  52. }
  53.  
  54. /* Gathers the input stream into a buffer until one of two things occur:
  55.  
  56.    1. We read a '%' followed by a '%'
  57.    2. We read a '%' followed by a '}'
  58.  
  59.    The first symbolizes the beginning of the keyword list proper,
  60.    The second symbolizes the end of the C source code to be generated
  61.    verbatim in the output file.
  62.  
  63.    I assume that the keys are separated from the optional preceding struct
  64.    declaration by a consecutive % followed by either % or } starting in 
  65.    the first column. The code below uses an expandible buffer to scan off 
  66.    and return a pointer to all the code (if any) appearing before the delimiter. */
  67.  
  68. char *
  69. Key_List::get_special_input (char delimiter)
  70. { 
  71.   T (Trace t ("Key_List::get_special_input");)
  72.   int size  = 80;
  73.   char *buf = new char[size];
  74.   int c, i;
  75.  
  76.   for (i = 0; (c = getchar ()) != EOF; i++)
  77.     {
  78.       if (c == '%')
  79.         {
  80.           if ((c = getchar ()) == delimiter)
  81.             {
  82.         
  83.               while ((c = getchar ()) != '\n')
  84.                 ; /* discard newline */
  85.               
  86.               if (i == 0)
  87.                 return "";
  88.               else
  89.                 {
  90.                   buf[delimiter == '%' && buf[i - 2] == ';' ? i - 2 : i - 1] = '\0';
  91.                   return buf;
  92.                 }
  93.             }
  94.           else
  95.             buf[i++] = '%';
  96.         }
  97.       else if (i >= size) /* Yikes, time to grow the buffer! */
  98.         { 
  99.           char *temp = new char[size *= 2];
  100.           int j;
  101.           
  102.           for (j = 0; j < i; j++)
  103.             temp[j] = buf[j];
  104.           
  105.           buf = temp;
  106.         }
  107.       buf[i] = c;
  108.     }
  109.   
  110.   return 0;        /* Problem here. */
  111. }
  112.  
  113. /* Stores any C text that must be included verbatim into the 
  114.    generated code output. */
  115.  
  116. char *
  117. Key_List::save_include_src (void)
  118. {
  119.   T (Trace t ("Key_List::save_include_src");)
  120.   int c;
  121.   
  122.   if ((c = getchar ()) != '%')
  123.     ungetc (c, stdin);
  124.   else if ((c = getchar ()) != '{')
  125.     report_error ("internal error, %c != '{' on line %d in file %s%a", c, __LINE__, __FILE__, 1);
  126.   else 
  127.     return get_special_input ('}');
  128.   return "";
  129. }
  130.  
  131. /* Determines from the input file whether the user wants to build a table
  132.    from a user-defined struct, or whether the user is content to simply
  133.    use the default array of keys. */
  134.  
  135. char *
  136. Key_List::get_array_type (void)
  137. {
  138.   T (Trace t ("Key_List::get_array_type");)
  139.   return get_special_input ('%');
  140. }  
  141.   
  142. /* strcspn - find length of initial segment of S consisting entirely
  143.    of characters not from REJECT (borrowed from Henry Spencer's
  144.    ANSI string package, when GNU libc comes out I'll replace this...). */
  145.  
  146. static inline int
  147. Key_List::strcspn (const char *s, const char *reject)
  148. {
  149.   T (Trace t ("Key_List::strcspn");)
  150.   const char *scan;
  151.   const char *rej_scan;
  152.   int   count = 0;
  153.  
  154.   for (scan = s; *scan; scan++) 
  155.     {
  156.  
  157.       for (rej_scan = reject; *rej_scan; rej_scan++)
  158.         if (*scan == *rej_scan)
  159.           return count;
  160.  
  161.       count++;
  162.     }
  163.  
  164.   return count;
  165. }
  166.  
  167. /* Sets up the Return_Type, the Struct_Tag type and the Array_Type
  168.    based upon various user Options. */
  169.  
  170. void 
  171. Key_List::set_output_types (void)
  172. {
  173.   T (Trace t ("Key_List::set_output_types");)
  174.   if (option[TYPE] && !(array_type = get_array_type ()))
  175.     return;                     /* Something's wrong, bug we'll catch it later on.... */
  176.   else if (option[TYPE])        /* Yow, we've got a user-defined type... */
  177.     {    
  178.       int struct_tag_length = strcspn (array_type, "{\n\0");
  179.       
  180.       if (option[POINTER])      /* And it must return a pointer... */
  181.         {    
  182.           return_type = new char[struct_tag_length + 2];
  183.           strncpy (return_type, array_type, struct_tag_length);
  184.           return_type[struct_tag_length] = '*';
  185.           return_type[struct_tag_length + 1] = '\0';
  186.         }
  187.       
  188.       struct_tag = new char[struct_tag_length + 1];
  189.       strncpy (struct_tag, array_type,  struct_tag_length);
  190.       struct_tag[struct_tag_length] = '\0';
  191.     }  
  192.   else if (option[POINTER])     /* Return a char *. */
  193.     return_type = default_array_type;
  194. }
  195.  
  196. /* Reads in all keys from standard input and creates a linked list pointed
  197.    to by Head.  This list is then quickly checked for ``links,'' i.e.,
  198.    unhashable elements possessing identical key sets and lengths. */
  199.  
  200. void 
  201. Key_List::read_keys (void)
  202. {
  203.   T (Trace t ("Key_List::read_keys");)
  204.   char *ptr;
  205.   
  206.   include_src = save_include_src ();
  207.   set_output_types ();
  208.   
  209.   /* Oops, problem with the input file. */  
  210.   if (! (ptr = Read_Line::get_line ()))
  211.     report_error ("No words in input file, did you forget to prepend %s"
  212.                   " or use -t accidentally?\n%a", "%%", 1);
  213.   
  214.   /* Read in all the keywords from the input file. */
  215.   else 
  216.     {                      
  217.       const char *delimiter = option.get_delimiter ();
  218.       List_Node  *temp, *trail = 0;
  219.  
  220.       head = new List_Node (ptr, strcspn (ptr, delimiter));
  221.       
  222.       for (temp = head;
  223.            (ptr = Read_Line::get_line ()) && strcmp (ptr, "%%");
  224.            temp = temp->next)
  225.         {
  226.           temp->next = new List_Node (ptr, strcspn (ptr, delimiter));
  227.           total_keys++;
  228.         }
  229.  
  230.       /* See if any additional C code is included at end of this file. */
  231.       if (ptr)
  232.         additional_code = 1;
  233.       
  234.       /* Hash table this number of times larger than keyword number. */
  235.       int table_size = (list_len = total_keys) * TABLE_MULTIPLE;
  236.  
  237.       /* By allocating the memory here we save on dynamic allocation overhead. 
  238.          Table must be a power of 2 for the hash function scheme to work. */
  239.       List_Node *table[POW (table_size)];
  240.  
  241.       /* Make large hash table for efficiency. */
  242.       Hash_Table found_link (table, table_size);
  243.  
  244.       /* Test whether there are any links and also set the maximum length of
  245.         an identifier in the keyword list. */
  246.       
  247.       for (temp = head; temp; temp = temp->next)
  248.         {
  249.           List_Node *ptr = found_link (temp, option[NOLENGTH]);
  250.           
  251.           /* Check for links.  We deal with these by building an equivalence class
  252.              of all duplicate values (i.e., links) so that only 1 keyword is
  253.              representative of the entire collection.  This *greatly* simplifies
  254.              processing during later stages of the program. */
  255.  
  256.           if (ptr)              
  257.             {                   
  258.               total_duplicates++;
  259.               list_len--;
  260.               trail->next = temp->next;
  261.               temp->link  = ptr->link;
  262.               ptr->link   = temp;
  263.  
  264.               /* Complain if user hasn't enabled the duplicate option. */
  265.               if (!option[DUP] || option[DEBUG])
  266.                 report_error ("Key link: \"%s\" = \"%s\", with key set \"%s\".\n",
  267.                               temp->key, ptr->key, temp->char_set);
  268.             }
  269.           else
  270.             trail = temp;
  271.             
  272.           /* Update minimum and maximum keyword length, if needed. */
  273.           max_key_len >?= temp->length;
  274.           min_key_len <?= temp->length;
  275.         }
  276.  
  277.       /* Exit program if links exists and option[DUP] not set, since we can't continue */
  278.       if (total_duplicates)
  279.         report_error (option[DUP]
  280.                       ? "%d input keys have identical hash values, examine output carefully...\n"
  281.                       : "%d input keys have identical hash values,\ntry different key positions or use option -D.\n%a", total_duplicates, 1);
  282.       if (option[ALLCHARS])
  283.         option.set_keysig_size (max_key_len);
  284.     }
  285. }
  286.  
  287. /* Recursively merges two sorted lists together to form one sorted list. The
  288.    ordering criteria is by frequency of occurrence of elements in the key set
  289.    or by the hash value.  This is a kludge, but permits nice sharing of
  290.    almost identical code without incurring the overhead of a function
  291.    call comparison. */
  292.   
  293. List_Node *
  294. Key_List::merge (List_Node *list1, List_Node *list2)
  295. {
  296.   T (Trace t ("Key_List::merge");)
  297.   if (!list1)
  298.     return list2;
  299.   else if (!list2)
  300.     return list1;
  301.   else if (occurrence_sort && list1->occurrence < list2->occurrence
  302.            || hash_sort && list1->hash_value > list2->hash_value)
  303.     {
  304.       list2->next = merge (list2->next, list1);
  305.       return list2;
  306.     }
  307.   else
  308.     {
  309.       list1->next = merge (list1->next, list2);
  310.       return list1;
  311.     }
  312. }
  313.  
  314. /* Applies the merge sort algorithm to recursively sort the key list by
  315.    frequency of occurrence of elements in the key set. */
  316.   
  317. List_Node *
  318. Key_List::merge_sort (List_Node *head)
  319. { 
  320.   T (Trace t ("Key_List::merge_sort");)
  321.   if (!head || !head->next)
  322.     return head;
  323.   else
  324.     {
  325.       List_Node *middle = head;
  326.       List_Node *temp   = head->next->next;
  327.     
  328.       while (temp)
  329.         {
  330.           temp   = temp->next;
  331.           middle = middle->next;
  332.           if (temp)
  333.             temp = temp->next;
  334.         } 
  335.     
  336.       temp         = middle->next;
  337.       middle->next = 0;
  338.       return merge (merge_sort (head), merge_sort (temp));
  339.     }   
  340. }
  341.  
  342. /* Returns the frequency of occurrence of elements in the key set. */
  343.  
  344. static inline int 
  345. Key_List::get_occurrence (List_Node *ptr)
  346. {
  347.   T (Trace t ("Key_List::get_occurrence");)
  348.   int value = 0;
  349.  
  350.   for (char *temp = ptr->char_set; *temp; temp++)
  351.     value += occurrences[*temp];
  352.   
  353.   return value;
  354. }
  355.  
  356. /* Enables the index location of all key set elements that are now 
  357.    determined. */
  358.   
  359. static inline void 
  360. Key_List::set_determined (List_Node *ptr)
  361. {
  362.   T (Trace t ("Key_List::set_determined");)
  363.   for (char *temp = ptr->char_set; *temp; temp++)
  364.     determined[*temp] = 1;
  365. }
  366.  
  367. /* Returns TRUE if PTR's key set is already completely determined. */
  368.  
  369. static inline int  
  370. Key_List::already_determined (List_Node *ptr)
  371. {
  372.   T (Trace t ("Key_List::already_determined");)
  373.   int is_determined = 1;
  374.  
  375.   for (char *temp = ptr->char_set; is_determined && *temp; temp++)
  376.     is_determined = determined[*temp];
  377.   
  378.   return is_determined;
  379. }
  380.  
  381. /* Reorders the table by first sorting the list so that frequently occuring 
  382.    keys appear first, and then the list is reorded so that keys whose values 
  383.    are already determined will be placed towards the front of the list.  This
  384.    helps prune the search time by handling inevitable collisions early in the
  385.    search process.  See Cichelli's paper from Jan 1980 JACM for details.... */
  386.  
  387. void 
  388. Key_List::reorder (void)
  389. {
  390.   T (Trace t ("Key_List::reorder");)
  391.   for (List_Node *ptr = head; ptr; ptr = ptr->next)
  392.     ptr->occurrence = get_occurrence (ptr);
  393.   
  394.   occurrence_sort = !(hash_sort = 0); /* Pretty gross, eh?! */
  395.   
  396.   for (ptr = head = merge_sort (head); ptr->next; ptr = ptr->next)
  397.     {
  398.       set_determined (ptr);
  399.     
  400.       if (already_determined (ptr->next))
  401.         continue;
  402.       else
  403.         {
  404.           List_Node *trail_ptr = ptr->next;
  405.           List_Node *run_ptr   = trail_ptr->next;
  406.       
  407.           for (; run_ptr; run_ptr = trail_ptr->next)
  408.             {
  409.         
  410.               if (already_determined (run_ptr))
  411.                 {
  412.                   trail_ptr->next = run_ptr->next;
  413.                   run_ptr->next   = ptr->next;
  414.                   ptr = ptr->next = run_ptr;
  415.                 }
  416.               else
  417.                 trail_ptr = run_ptr;
  418.             }
  419.         }
  420.     }     
  421. }
  422.  
  423. /* Outputs the maximum and minimum hash values.  Since the
  424.    list is already sorted by hash value all we need to do is
  425.    find the final item! */
  426.   
  427. void
  428. Key_List::output_min_max ()
  429. {
  430.   T (Trace t ("Key_List::output_min_max");)
  431.   for (List_Node *temp = head; temp->next; temp = temp->next)
  432.     ;
  433.  
  434.   min_hash_value = head->hash_value;
  435.   max_hash_value = temp->hash_value;
  436.  
  437.   if (!option[ENUM])
  438.     printf ("\n#define TOTAL_KEYWORDS %d\n#define MIN_WORD_LENGTH %d"
  439.             "\n#define MAX_WORD_LENGTH %d\n#define MIN_HASH_VALUE %d"
  440.             "\n#define MAX_HASH_VALUE %d\n", total_keys, min_key_len,
  441.             max_key_len, min_hash_value, max_hash_value);
  442.   printf ("/* maximum key range = %d, duplicates = %d */\n\n",
  443.           max_hash_value - min_hash_value + 1, total_duplicates);
  444. }
  445.  
  446. /* Generates the output using a C switch.  This trades increased search
  447.    time for decreased table space (potentially *much* less space for
  448.    sparse tables). It the user has specified their own struct in the
  449.    keyword file *and* they enable the POINTER option we have extra work to
  450.    do.  The solution here is to maintain a local static array of user
  451.    defined struct's, as with the Output_Lookup_Function.  Then we use for
  452.    switch statements to perform either a strcmp or strncmp, returning 0 if
  453.    the str fails to match, and otherwise returning a pointer to appropriate index
  454.    location in the local static array. */
  455.  
  456. void 
  457. Key_List::output_switch (void)
  458. {
  459.   T (Trace t ("Key_List::output_switch");)
  460.   char      *comp_buffer;
  461.   List_Node *curr                     = head;
  462.   int        pointer_and_type_enabled = option[POINTER] && option[TYPE];
  463.   int        total_switches           = option.get_total_switches ();
  464.   int        switch_size              = keyword_list_length () / total_switches;
  465.  
  466.   if (pointer_and_type_enabled)
  467.     {
  468.       comp_buffer = (char *) alloca (strlen ("*str == *resword->%s && !strncmp (str + 1, resword->%s + 1, len - 1)")
  469.                                              + 2 * strlen (option.get_key_name ()) + 1);
  470.       sprintf (comp_buffer, option[COMP]
  471.                ? "*str == *resword->%s && !strncmp (str + 1, resword->%s + 1, len - 1)"
  472.                : "*str == *resword->%s && !strcmp (str + 1, resword->%s + 1)",
  473.                option.get_key_name (), option.get_key_name ());
  474.     }
  475.   else
  476.     comp_buffer = option[COMP]
  477.       ? "*str == *resword && !strncmp (str + 1, resword + 1, len - 1)"
  478.       : "*str == *resword && !strcmp (str + 1, resword + 1)";
  479.  
  480.   printf ("  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n    {\n"
  481.           "      register int key = %s (str, len);\n\n"
  482.           "      if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n        {\n",
  483.           option.get_hash_name ());
  484.   
  485.   /* Properly deal with user's who request multiple switch statements. */
  486.  
  487.   while (curr)
  488.     {
  489.       List_Node *temp              = curr;
  490.       int        lowest_case_value = curr->hash_value;
  491.       int        number_of_cases   = 0;
  492.  
  493.       /* Figure out a good cut point to end this switch. */
  494.  
  495.       for (; temp && ++number_of_cases < switch_size; temp = temp->next)
  496.         if (temp->next && temp->hash_value == temp->next->hash_value)
  497.           while (temp->next && temp->hash_value == temp->next->hash_value)
  498.             temp = temp->next;
  499.  
  500.       if (temp && total_switches != 1)
  501.         printf ("          if (key <= %d)\n            {\n", temp->hash_value);
  502.       else
  503.         printf ("            {\n");
  504.  
  505.       /* Output each keyword as part of a switch statement indexed by hash value. */
  506.       
  507.      if (option[POINTER] || option[DUP])
  508.         {
  509.           int i = 0;
  510.  
  511.           printf ("              %s%s *resword; %s\n\n",
  512.                   option[CONST] ? "const " : "",
  513.                   pointer_and_type_enabled ? struct_tag : "char",
  514.                   option[LENTABLE] && !option[DUP] ? "int key_len;" : "");
  515.           if (total_switches == 1)
  516.             {
  517.               printf ("              switch (key)\n                {\n");
  518.               lowest_case_value = 0;
  519.             }
  520.           else
  521.             printf ("              switch (key - %d)\n                {\n", lowest_case_value);
  522.  
  523.           for (temp = curr; temp && ++i <= number_of_cases; temp = temp->next)
  524.             {
  525.               printf ("                case %*d:", field_width, temp->hash_value - lowest_case_value);
  526.               if (option[DEBUG])
  527.                 printf (" /* hash value = %4d, keyword = \"%s\" */", temp->hash_value, temp->key);
  528.               putchar ('\n');
  529.  
  530.               /* Handle `natural links,' i.e., those that occur statically. */
  531.  
  532.               if (temp->link)
  533.                 {
  534.                   List_Node *links;
  535.  
  536.                   for (links = temp; links; links = links->link)
  537.                     {
  538.                       if (pointer_and_type_enabled)
  539.                         printf ("                  resword = &wordlist[%d];\n", links->index);
  540.                       else
  541.                         printf ("                  resword = \"%s\";\n", links->key); 
  542.                       printf ("                  if (%s) return resword;\n", comp_buffer);
  543.                     }
  544.                 }
  545.               /* Handle unresolved duplicate hash values.  These are guaranteed
  546.                 to be adjacent since we sorted the keyword list by increasing
  547.                   hash values. */
  548.               if (temp->next && temp->hash_value == temp->next->hash_value)
  549.                 {
  550.  
  551.                   for ( ; temp->next && temp->hash_value == temp->next->hash_value;
  552.                        temp = temp->next)
  553.                     {
  554.                       if (pointer_and_type_enabled)
  555.                         printf ("                  resword = &wordlist[%d];\n", temp->index);
  556.                       else
  557.                         printf ("                  resword = \"%s\";\n", temp->key);
  558.                       printf ("                  if (%s) return resword;\n", comp_buffer);
  559.                     }
  560.                   if (pointer_and_type_enabled)
  561.                     printf ("                  resword = &wordlist[%d];\n", temp->index);
  562.                   else
  563.                     printf ("                  resword = \"%s\";\n", temp->key);
  564.                   printf ("                  return %s ? resword : 0;\n", comp_buffer);
  565.                 }
  566.               else if (temp->link)
  567.                 printf ("                  return 0;\n");
  568.               else
  569.                 {
  570.                   if (pointer_and_type_enabled)
  571.                     printf ("                  resword = &wordlist[%d];", temp->index);
  572.                   else 
  573.                     printf ("                  resword = \"%s\";", temp->key);
  574.                   if (option[LENTABLE] && !option[DUP])
  575.                     printf (" key_len = %d;", temp->length);
  576.                   printf (" break;\n");
  577.                 }
  578.             }
  579.           printf ("                default: return 0;\n                }\n");
  580.           printf (option[LENTABLE] && !option[DUP]
  581.                   ? "              if (len == key_len && %s)\n                return resword;\n"
  582.                   : "              if (%s)\n                return resword;\n", comp_buffer);
  583.           printf ("              return 0;\n            }\n");
  584.           curr = temp;
  585.         }
  586.       else                          /* Nothing special required here. */
  587.         {                        
  588.           int i = 0;
  589.           printf ("              char *s;\n\n              switch (key - %d)\n                {\n",
  590.                   lowest_case_value);
  591.       
  592.           for (temp = curr; temp && ++i <= number_of_cases; temp = temp->next)
  593.             if (option[LENTABLE])
  594.               printf ("                case %*d: if (len == %d) s = \"%s\"; else return 0; break;\n",
  595.                       field_width, temp->hash_value - lowest_case_value, 
  596.                       temp->length, temp->key);
  597.             else
  598.               printf ("                case %*d: s = \"%s\"; break;\n",
  599.                       field_width, temp->hash_value - lowest_case_value, temp->key);
  600.                       
  601.           printf ("                default: return 0;\n                }\n              ");
  602.           printf ("return *s == *str && !%s;\n            }\n",
  603.                   option[COMP]
  604.                   ? "strncmp (s + 1, str + 1, len - 1)" : "strcmp (s + 1, str + 1)");
  605.           curr = temp;
  606.         }
  607.     }
  608.   printf ("         }\n    }\n  return 0;\n}\n");
  609. }
  610.  
  611. /* Prints out a table of keyword lengths, for use with the 
  612.    comparison code in generated function ``in_word_set.'' */
  613.  
  614. void 
  615. Key_List::output_keylength_table (void)
  616. {
  617.   T (Trace t ("Key_List::output_keylength_table");)
  618.   const int  max_column = 15;
  619.   int        index      = 0;
  620.   int        column     = 0;
  621.   char      *indent     = option[GLOBAL] ? "" : "  ";
  622.   List_Node *temp;
  623.  
  624.   if (!option[DUP] && !option[SWITCH]) 
  625.     {
  626.       printf ("\n%sstatic %sunsigned %s lengthtable[] =\n%s%s{\n    ",
  627.               indent, option[CONST] ? "const " : "",
  628.               max_key_len <= MAX_UNSIGNED_CHAR ? "char" : (max_key_len <= MAX_UNSIGNED_SHORT ? "short" : "long"),
  629.               indent, indent);
  630.   
  631.       for (temp = head; temp; temp = temp->next, index++)
  632.         {
  633.     
  634.           if (index < temp->hash_value)
  635.             for ( ; index < temp->hash_value; index++)
  636.               printf ("%3d,%s", 0, ++column % (max_column - 1) ? "" : "\n    ");
  637.     
  638.           printf ("%3d,%s", temp->length, ++column % (max_column - 1 ) ? "" : "\n    ");
  639.         }
  640.   
  641.       printf ("\n%s%s};\n", indent, indent);
  642.     }
  643. }
  644. /* Prints out the array containing the key words for the Gen_Perf
  645.    hash function. */
  646.   
  647. void 
  648. Key_List::output_keyword_table (void)
  649. {
  650.   T (Trace t ("Key_List::output_keyword_table");)
  651.   char      *l_brace = *head->rest ? "{" : "";
  652.   char      *r_brace = *head->rest ? "}," : "";
  653.   char      *indent  = option[GLOBAL] ? "" : "  ";
  654.   int        index   = 0;
  655.   List_Node *temp;
  656.  
  657.   printf ("%sstatic %s%swordlist[] =\n%s%s{\n",
  658.           indent, option[CONST] ? "const " : "", struct_tag, indent, indent);
  659.  
  660.   /* Skip over leading blank entries if there are no duplicates. */
  661.  
  662.   printf ("      ");
  663.   for (int column = 1; index < head->hash_value; index++, column++)
  664.     printf ("%s\"\",%s %s", l_brace, r_brace, column % 9 ? "" : "\n      ");      
  665.   if (column % 10)
  666.     printf ("\n");
  667.  
  668.           
  669.   /* Generate an array of reserved words at appropriate locations. */
  670.   
  671.   for (temp = head ; temp; temp = temp->next, index++)
  672.     {
  673.       temp->index = index;
  674.  
  675.       if (!option[SWITCH] && (total_duplicates == 0 || !option[DUP]) && index < temp->hash_value)
  676.         {
  677.           int column;
  678.  
  679.           printf ("      ");
  680.       
  681.           for (column = 1; index < temp->hash_value; index++, column++)
  682.             printf ("%s\"\",%s %s", l_brace, r_brace, column % 9 ? "" : "\n      ");
  683.       
  684.           if (column % 10)
  685.             printf ("\n");
  686.           else 
  687.             {
  688.               printf ("%s\"%s\", %s%s", l_brace, temp->key, temp->rest, r_brace);
  689.               if (option[DEBUG])
  690.                 printf (" /* hash value = %d, index = %d */", temp->hash_value, temp->index);
  691.               putchar ('\n');
  692.               continue;
  693.             }
  694.         }
  695.  
  696.       printf ("      %s\"%s\", %s%s", l_brace, temp->key, temp->rest, r_brace);
  697.       if (option[DEBUG])
  698.         printf (" /* hash value = %d, index = %d */", temp->hash_value, temp->index);
  699.       putchar ('\n');
  700.  
  701.       /* Deal with links specially. */
  702.       if (temp->link)
  703.         for (List_Node *links = temp->link; links; links = links->link)
  704.           {
  705.             links->index = ++index;
  706.             printf ("      %s\"%s\", %s%s", l_brace, links->key, links->rest, r_brace);
  707.             if (option[DEBUG])
  708.               printf (" /* hash value = %d, index = %d */", links->hash_value, links->index);
  709.             putchar ('\n');
  710.           }
  711.     }
  712.   printf ("%s%s};\n\n", indent, indent);
  713. }
  714.  
  715. /* Generates C code for the hash function that returns the
  716.    proper encoding for each key word. */
  717.  
  718. void 
  719. Key_List::output_hash_function (void)
  720. {
  721.   T (Trace t ("Key_List::output_hash_function");)
  722.   const int max_column  = 10;
  723.   int       count       = max_hash_value;
  724.  
  725.   /* Calculate maximum number of digits required for MAX_HASH_VALUE. */
  726.  
  727.   for (field_width = 2; (count /= 10) > 0; field_width++)
  728.     ;
  729.  
  730.   if (option[GNU])
  731.     printf ("#ifdef __GNUC__\ninline\n#endif\n");
  732.   
  733.   if (option[C])
  734.     printf ("static ");
  735.   printf ("unsigned int\n");
  736.   if (option[CPLUSPLUS])
  737.     printf ("%s::", option.get_class_name ());
  738.  
  739.   printf (option[ANSI] 
  740.           ? "%s (register const char *str, register int len)\n{\n  static %sunsigned %s asso_values[] =\n    {"
  741.           : "%s (str, len)\n     register char *str;\n     register int unsigned len;\n{\n  static %sunsigned %s asso_values[] =\n    {",
  742.           option.get_hash_name (), option[CONST] ? "const " : "",
  743.           max_hash_value <= MAX_UNSIGNED_CHAR ? "char" : (max_hash_value <= MAX_UNSIGNED_SHORT ? "short" : "int"));
  744.   
  745.   for (count = 0; count < ALPHA_SIZE; ++count)
  746.     {
  747.       if (!(count % max_column))
  748.         printf ("\n    ");
  749.       
  750.       printf ("%*d,", field_width, occurrences[count] ? asso_values[count] : max_hash_value + 1);
  751.     }
  752.   
  753.   /* Optimize special case of ``-k 1,$'' */
  754.   if (option[DEFAULTCHARS]) 
  755.     printf ("\n    };\n  return %sasso_values[str[len - 1]] + asso_values[str[0]];\n}\n\n",
  756.             option[NOLENGTH] ? "" : "len + ");
  757.   else
  758.     {
  759.       int key_pos;
  760.  
  761.       option.reset ();
  762.  
  763.       /* Get first (also highest) key position. */
  764.       key_pos = option.get (); 
  765.       
  766.       /* We can perform additional optimizations here. */
  767.       if (!option[ALLCHARS] && key_pos <= min_key_len) 
  768.         { 
  769.           printf ("\n    };\n  return %s", option[NOLENGTH] ? "" : "len + ");
  770.  
  771.           for (; key_pos != WORD_END; )
  772.             {
  773.               printf ("asso_values[str[%d]]", key_pos - 1);
  774.               if ((key_pos = option.get ()) != EOS)
  775.                 printf (" + ");
  776.               else
  777.                 break;
  778.             }
  779.  
  780.           printf ("%s;\n}\n\n", key_pos == WORD_END ? "asso_values[str[len - 1]]" : "");
  781.         }
  782.  
  783.       /* We've got to use the correct, but brute force, technique. */
  784.       else 
  785.         {                    
  786.           printf ("\n    };\n  register int hval = %s;\n\n  switch (%s)\n    {\n      default:\n",
  787.                   option[NOLENGTH] ? "0" : "len", option[NOLENGTH] ? "len" : "hval");
  788.           
  789.           /* User wants *all* characters considered in hash. */
  790.           if (option[ALLCHARS]) 
  791.             { 
  792.               int i;
  793.  
  794.               for (i = max_key_len; i > 0; i--)
  795.                 printf ("      case %d:\n        hval += asso_values[str[%d]];\n", i, i - 1);
  796.               
  797.               printf ("    }\n  return hval;\n}\n\n");
  798.             }
  799.           else                  /* do the hard part... */
  800.             {                
  801.               count = key_pos + 1;
  802.               
  803.               do
  804.                 {
  805.                   
  806.                   while (--count > key_pos)
  807.                     printf ("      case %d:\n", count);
  808.                   
  809.                   printf ("      case %d:\n        hval += asso_values[str[%d]];\n",
  810.                           key_pos, key_pos - 1);
  811.                 }
  812.               while ((key_pos = option.get ()) != EOS && key_pos != WORD_END);
  813.               
  814.               printf ("    }\n  return hval%s;\n}\n\n",
  815.                       key_pos == WORD_END ? " + asso_values[str[len - 1]]" : "");
  816.             }
  817.         }
  818.     }
  819. }
  820.  
  821. /* Generates the large, sparse table that maps hash values into
  822.    the smaller, contiguous range of the keyword table. */
  823.  
  824. void
  825. Key_List::output_lookup_array (void)
  826. {
  827.   T (Trace t ("Key_List::output_lookup_array");)
  828.   if (total_duplicates > 0)
  829.     {
  830.       const int DEFAULT_VALUE = -1;
  831.  
  832.       struct 
  833.         {
  834.           int hash_value;       /* Hash value for this particular duplicate set. */
  835.           int index;            /* Index into the main keyword storage array. */
  836.           int count;            /* Number of consecutive duplicates at this index. */
  837.         } duplicates[total_duplicates], *dup_ptr = duplicates;
  838.       int lookup_array[max_hash_value + 1], *lookup_ptr = lookup_array + max_hash_value + 1;
  839.  
  840.       while (lookup_ptr > lookup_array)
  841.         *--lookup_ptr = DEFAULT_VALUE;
  842.   
  843.       for (List_Node *temp = head; temp; temp = temp->next)
  844.         {
  845.           int hash_value = temp->hash_value;
  846.           lookup_array[hash_value] = temp->index;
  847.           if (option[DEBUG])
  848.             fprintf (stderr, "keyword = %s, index = %d\n", temp->key, temp->index);
  849.           if (!temp->link &&
  850.               (!temp->next || hash_value != temp->next->hash_value))
  851.             continue;
  852.           *dup_ptr = (typeof (*dup_ptr)) { hash_value, temp->index, 1 };
  853.           
  854.           for (List_Node *ptr = temp->link; ptr; ptr = ptr->link)
  855.             {
  856.               dup_ptr->count++;
  857.               if (option[DEBUG])
  858.                 fprintf (stderr, "static linked keyword = %s, index = %d\n", ptr->key, ptr->index);            
  859.             }
  860.  
  861.           while (temp->next && hash_value == temp->next->hash_value)
  862.             {
  863.               temp = temp->next;
  864.               dup_ptr->count++;
  865.               if (option[DEBUG])
  866.                 fprintf (stderr, "dynamic linked keyword = %s, index = %d\n", temp->key, temp->index);
  867.  
  868.               for (List_Node *ptr = temp->link; ptr; ptr = ptr->link)
  869.                 {
  870.                   dup_ptr->count++;
  871.                   if (option[DEBUG])
  872.                     fprintf (stderr, "static linked keyword = %s, index = %d\n", ptr->key, ptr->index);            
  873.                 }
  874.             }
  875.           dup_ptr++;
  876.         }
  877.   
  878.       while (--dup_ptr >= duplicates)
  879.         {
  880.           if (option[DEBUG])
  881.             fprintf (stderr, "dup_ptr[%d]: hash_value = %d, index = %d, count = %d\n",
  882.                      dup_ptr - duplicates, dup_ptr->hash_value, dup_ptr->index, dup_ptr->count);
  883.  
  884.           /* Start searching for available space towards the right part of the lookup array. */
  885.           for (int i = dup_ptr->hash_value; i < max_hash_value; i++)
  886.             if (lookup_array[i] == DEFAULT_VALUE && lookup_array[i + 1] == DEFAULT_VALUE)
  887.               {
  888.                 lookup_array[i] = -dup_ptr->index;
  889.                 lookup_array[i + 1] = -dup_ptr->count;
  890.                 lookup_array[dup_ptr->hash_value] = max_hash_value + (i - dup_ptr->hash_value);
  891.                 break;
  892.               }
  893.  
  894.           /* If we didn't find it to the right look to the left instead... */
  895.           if (i == max_hash_value)
  896.             {
  897.  
  898.               for (i = dup_ptr->hash_value; i > 0; i--)
  899.                 if (lookup_array[i] == DEFAULT_VALUE && lookup_array[i - 1] == DEFAULT_VALUE)
  900.                   {
  901.                     lookup_array[i - 1] = -dup_ptr->index;
  902.                     lookup_array[i] = -dup_ptr->count;
  903.                     lookup_array[dup_ptr->hash_value] = -(max_hash_value + (dup_ptr->hash_value - i + 1));
  904.                     break;
  905.                   }
  906.  
  907.               /* We are in *big* trouble if this happens! */
  908.               assert (i != 0);
  909.             }
  910.         }
  911.  
  912.       int max = MIN_INT;
  913.  
  914.       for (lookup_ptr = lookup_array + max_hash_value + 1; lookup_ptr > lookup_array; max >?= abs (*--lookup_ptr))
  915.         ;
  916.  
  917.       char *indent = option[GLOBAL] ? "" : "  ";
  918.       printf ("%sstatic %s%s lookup[] =\n%s%s{\n      ", indent, option[CONST] ? "const " : "",
  919.               max <= MAX_SIGNED_CHAR ? "char" : (max <= MAX_SIGNED_SHORT ? "short" : "int"),
  920.               indent, indent);
  921.  
  922.       int count = max;
  923.  
  924.       /* Calculate maximum number of digits required for MAX_HASH_VALUE. */
  925.  
  926.       for (field_width = 2; (count /= 10) > 0; field_width++)
  927.         ;
  928.  
  929.       const int max_column = 15;
  930.       int column = 0;
  931.  
  932.       for (lookup_ptr = lookup_array; 
  933.            lookup_ptr < lookup_array + max_hash_value + 1;
  934.            lookup_ptr++)
  935.         printf ("%*d,%s", field_width, *lookup_ptr, ++column % (max_column - 1) ? "" : "\n      ");
  936.  
  937.       printf ("\n%s%s};\n\n", indent, indent);
  938.     }
  939. }
  940. /* Generates C code to perform the keyword lookup. */
  941.  
  942. void 
  943. Key_List::output_lookup_function (void)
  944. { 
  945.   T (Trace t ("Key_List::output_lookup_function");)
  946.   printf ("  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n    {\n"
  947.           "      register int key = %s (str, len);\n\n"
  948.           "      if (key <= MAX_HASH_VALUE && key >= 0)\n        {\n",
  949.           option.get_hash_name ());
  950.   
  951.   if (option[DUP] && total_duplicates > 0)
  952.     {
  953.       printf ("          register int index = lookup[key];\n\n"
  954.               "          if (index >= 0 && index < MAX_HASH_VALUE)\n"
  955.               "            {\n"
  956.               "              register %schar *s = wordlist[index]", option[CONST] ? "const " : "");
  957.       if (array_type != default_array_type)
  958.         printf (".%s", option.get_key_name ());
  959.   
  960.       printf (";\n\n              if (%s*s == *str && !%s)\n                return %s;\n            }\n",
  961.               option[LENTABLE] ? "len == lengthtable[key]\n              && " : "",
  962.               option[COMP] ? "strncmp (str + 1, s + 1, len - 1)" : "strcmp (str + 1, s + 1)",
  963.               option[TYPE] && option[POINTER] ? "&wordlist[index]" : "s");
  964.       printf ("          else if (index < 0 && index >= -MAX_HASH_VALUE)\n"
  965.               "            return 0;\n          else\n            {\n"
  966.               "              register int offset = key + index + (index > 0 ? -MAX_HASH_VALUE : MAX_HASH_VALUE);\n"
  967.               "              register %s%s*base = &wordlist[-lookup[offset]];\n"
  968.               "              register %s%s*ptr = base + -lookup[offset + 1];\n\n"
  969.               "              while (--ptr >= base)\n                ",
  970.               option[CONST] ? "const " : "", struct_tag,
  971.               option[CONST] ? "const " : "", struct_tag);
  972.       if (array_type != default_array_type)
  973.         printf ("if (*str == *ptr->%s && !strcmp (str + 1, ptr->%s + 1",
  974.                 option.get_key_name (), option.get_key_name ());
  975.       else
  976.         printf ("if (*str == **ptr && !strcmp (str + 1, *ptr + 1");
  977.  
  978.       printf ("))\n                  return %sptr;"
  979.               "\n            }\n        }\n    }\n  return 0;\n}\n", array_type == default_array_type ? "*" : "");
  980.               
  981.     }
  982.   else
  983.     {
  984.       printf ("          register %schar *s = wordlist[key]", option[CONST] ? "const " : "");
  985.  
  986.       if (array_type != default_array_type)
  987.         printf (".%s", option.get_key_name ());
  988.   
  989.       printf (";\n\n          if (%s*s == *str && !%s)\n            return %s",
  990.               option[LENTABLE] ? "len == lengthtable[key]\n              && " : "",
  991.               option[COMP] ? "strncmp (str + 1, s + 1, len - 1)" : "strcmp (str + 1, s + 1)",
  992.               option[TYPE] && option[POINTER] ? "&wordlist[key]" : "s");
  993.       printf (";\n        }\n    }\n  return 0;\n}\n");
  994.     }
  995. }
  996.  
  997. /* Generates the hash function and the key word recognizer function
  998.    based upon the user's Options. */
  999.  
  1000. void 
  1001. Key_List::output (void)
  1002. {
  1003.   T (Trace t ("Key_List::output");)
  1004.   printf ("%s\n", include_src);
  1005.   
  1006.   if (option[TYPE] && !option[NOTYPE]) /* Output type declaration now, reference it later on.... */
  1007.     printf ("%s;\n", array_type);
  1008.   
  1009.   output_min_max ();
  1010.  
  1011.   if (option[CPLUSPLUS])
  1012.     printf ("class %s\n{\nprivate:\n"
  1013.             "  static unsigned int hash (const char *str, int len);\npublic:\n"
  1014.             "  static %s%s%s (const char *str, int len);\n};\n\n",
  1015.             option.get_class_name (), option[CONST] ? "const " : "", 
  1016.             return_type, option.get_function_name ());
  1017.  
  1018.   output_hash_function ();
  1019.   
  1020.   if (option[GLOBAL])
  1021.     if (option[SWITCH])
  1022.       {
  1023.         if (option[LENTABLE] && option[DUP])
  1024.           output_keylength_table ();
  1025.         if (option[POINTER] && option[TYPE])
  1026.           output_keyword_table ();
  1027.       }
  1028.     else
  1029.       {
  1030.         if (option[LENTABLE])
  1031.           output_keylength_table ();
  1032.         output_keyword_table ();
  1033.         output_lookup_array ();
  1034.       }
  1035.   
  1036.   if (option[GNU])          /* Use the inline keyword to remove function overhead. */
  1037.     printf ("#ifdef __GNUC__\ninline\n#endif\n");
  1038.   
  1039.   printf ("%s%s\n", option[CONST] ? "const " : "", return_type);
  1040.   if (option[CPLUSPLUS])
  1041.     printf ("%s::", option.get_class_name ());
  1042.  
  1043.   printf (option[ANSI] 
  1044.           ? "%s (register const char *str, register int len)\n{\n"
  1045.           : "%s (str, len)\n     register char *str;\n     register unsigned int len;\n{\n",
  1046.           option.get_function_name ());
  1047.  
  1048.   if (option[ENUM])
  1049.     printf ("  enum\n    {\n"
  1050.             "      TOTAL_KEYWORDS = %d,\n"
  1051.             "      MIN_WORD_LENGTH = %d,\n"
  1052.             "      MAX_WORD_LENGTH = %d,\n"
  1053.             "      MIN_HASH_VALUE = %d,\n"
  1054.             "      MAX_HASH_VALUE = %d,\n"
  1055.             "    };\n\n",
  1056.             total_keys, min_key_len, max_key_len, min_hash_value, max_hash_value);
  1057.  
  1058.   /* Use the switch in place of lookup table. */
  1059.   if (option[SWITCH])
  1060.     {               
  1061.       if (!option[GLOBAL])
  1062.         {
  1063.           if (option[LENTABLE] && option[DUP])
  1064.             output_keylength_table ();
  1065.           if (option[POINTER] && option[TYPE]) 
  1066.             output_keyword_table ();
  1067.         }
  1068.       output_switch ();
  1069.     }
  1070.   /* Use the lookup table, in place of switch. */
  1071.   else                
  1072.     {           
  1073.       if (!option[GLOBAL])
  1074.         {
  1075.           if (option[LENTABLE])
  1076.             output_keylength_table ();
  1077.           output_keyword_table ();
  1078.         }
  1079.       if (!option[GLOBAL])
  1080.         output_lookup_array ();
  1081.       output_lookup_function ();
  1082.     }
  1083.   
  1084.   if (additional_code)
  1085.     for (int c; (c = getchar ()) != EOF; putchar (c))
  1086.       ;
  1087.  
  1088.   fflush (stdout);
  1089. }
  1090.  
  1091. /* Sorts the keys by hash value. */
  1092.  
  1093. void 
  1094. Key_List::sort (void) 
  1095. { 
  1096.   T (Trace t ("Key_List::sort");)
  1097.   hash_sort       = 1;
  1098.   occurrence_sort = 0;
  1099.   
  1100.   head = merge_sort (head);
  1101. }
  1102.  
  1103. /* Dumps the key list to stderr stream. */
  1104.  
  1105. void 
  1106. Key_List::dump () 
  1107. {      
  1108.   T (Trace t ("Key_List::dump");)
  1109.   int field_width = option.get_max_keysig_size ();
  1110.   
  1111.   fprintf (stderr, "\nList contents are:\n(hash value, key length, index, %*s, keyword):\n",
  1112.            field_width, "char_set");
  1113.   
  1114.   for (List_Node *ptr = head; ptr; ptr = ptr->next)
  1115.     fprintf (stderr, "%11d,%11d,%6d, %*s, %s\n",
  1116.              ptr->hash_value, ptr->length, ptr->index,
  1117.              field_width, ptr->char_set, ptr->key);
  1118. }
  1119.  
  1120. /* Simple-minded constructor action here... */
  1121.  
  1122. Key_List::Key_List (void) 
  1123. {   
  1124.   T (Trace t ("Key_List::Key_List");)
  1125.   total_keys       = 1;
  1126.   max_key_len      = MIN_INT;
  1127.   min_key_len      = MAX_INT;
  1128.   return_type      = default_return_type;
  1129.   array_type       = struct_tag  = default_array_type;
  1130.   head             = 0;
  1131.   total_duplicates = 0;
  1132.   additional_code  = 0;
  1133. }
  1134.  
  1135. /* Returns the length of entire key list. */
  1136.  
  1137. int 
  1138. Key_List::keyword_list_length (void) 
  1139. { 
  1140.   T (Trace t ("Key_List::keyword_list_length");)
  1141.   return list_len;
  1142. }
  1143.  
  1144. /* Returns length of longest key read. */
  1145.  
  1146. int 
  1147. Key_List::max_key_length (void) 
  1148. { 
  1149.   T (Trace t ("Key_List::max_key_length");)
  1150.   return max_key_len;
  1151. }
  1152.  
  1153.